/**
 * https://leetcode-cn.com/problems/sort-list/
 * 排序链表
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * 进阶：
 * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * @param head
 */
const sortList = (head: ListNode | null): ListNode | null => {
  // 边界判断
  if (head === null) return null;

  // 计算链表的总长度
  let n: ListNode | null = head;
  let len = 0;
  while (n !== null) {
    len++;
    n = n.next;
  }

  const dummyHead = new ListNode(0, head);
  for (let subI = 1; subI < len; subI <<= 1) {
    let prev = dummyHead, // for循环开始prev就指向dummyHead
      curr: ListNode | null = dummyHead.next;
    while (curr !== null) {
      const head1 = curr;

      // 进行拆分
      for (let i = 1; i < subI && curr.next !== null; i++) {
        curr = curr.next;
      }

      // 断开链表并且重新修改curr的指向
      const head2 = curr.next!;
      curr.next = null;
      curr = head2;

      // 再次划分
      for (let i = 1; i < subI && curr !== null && curr.next !== null; i++) {
        curr = curr.next;
      }

      let next = null;
      // 如果curr不为空, 保存next
      if (curr !== null) {
        next = curr.next;
        // next清空
        curr.next = null;
      }

      // 合并
      const merged = merge(head1, head2);

      prev.next = merged;

      // 修改prev为最后一个
      while (prev.next !== null) {
        prev = prev.next;
      }

      curr = next;
    }
  }

  return dummyHead.next;
};

/**
 * 合并两个有序的
 * @param left
 * @param right
 */
const merge = (left: ListNode | null, right: ListNode | null) => {
  const dummyHead = new ListNode(0);
  let head = dummyHead;

  while (left !== null && right !== null) {
    if (left.val < right.val) {
      // 左边比较小
      head = head.next = left;
      left = left.next;
    } else {
      // 右边比较小
      head = head.next = right;
      right = right.next;
    }
  }

  // 如果左边或者后边部分还没遍历完
  head.next = left === null ? right : left;

  return dummyHead.next;
};

const sortList2 = (head: ListNode | null): ListNode | null => {
  // 边界判断
  if (head === null || head.next === null) return head;

  const arr: ListNode[] = [];

  let tmp: ListNode | null = head;
  while (tmp !== null) {
    arr.push(tmp);
    // 指向下一个
    tmp = tmp.next;
  }

  /**
   * 快排
   * @param arr
   */
  const quickSort = (arr: ListNode[]) => {
    const sort = (arr: ListNode[], s: number, e: number) => {
      // 边界判断
      if (e - s < 2) return;
      // 得到pivot
      const m = partition(arr, s, e);

      // 继续拆分
      sort(arr, s, m);
      sort(arr, m + 1, e);
    };

    /**
     * 拆分
     * @param s
     * @param e
     */
    const partition = (arr: ListNode[], s: number, e: number) => {
      // 保存pivot
      const pivot = arr[s];

      /**
       * 与pivot比较
       * @param n
       * @returns
       */
      const compare = (n: number) => arr[n].val - pivot.val;

      /**
       * 替换位置
       * @param n
       * @returns
       */
      const replace = (l: number, r: number) => (arr[l] = arr[r]);
      e--;
      while (s < e) {
        // 从后往前比较
        while (s < e) {
          // 如果有比pivot小的, 替换s的位置
          if (compare(e) < 0) {
            // 替换位置
            replace(s, e);
            break; // 结束本轮的循环
          }
          // 往前
          e--;
        }

        // 从前开始比较, 如果有比pivot大的, 替换e的位置
        while (s < e) {
          if (compare(s) > 0) {
            // 替换位置
            replace(e, s);
            break; // 结束本轮循环
          }
          s++;
        }
      }

      arr[s] = pivot;
      return s;
    };

    sort(arr, 0, arr.length);
  };
  quickSort(arr);

  const dummyHead = new ListNode(0);
  let h = dummyHead;
  for (let l of arr) {
    h = h.next = l;
  }
  // 最后一个next为空
  h.next = null;

  return dummyHead.next;
};
